package cn.lbd.arithmetic.leetcode.editor.cn;
//给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
//
// 示例: 
//
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出:
//[
//  ["ate","eat","tea"],
//  ["nat","tan"],
//  ["bat"]
//] 
//
// 说明： 
//
// 
// 所有输入均为小写字母。 
// 不考虑答案输出的顺序。 
// 
// Related Topics 哈希表 字符串 
// 👍 479 👎 0


import java.util.*;
import java.util.concurrent.TimeUnit;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution49 {
    /*public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> strings = new ArrayList<>();
        //过滤已加入异位词集合的字符串
        boolean[] isJoin = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
            List<String> string = new ArrayList<>();
            //未被加入才去判断
            if (!isJoin[i]) {
                string.add(strs[i]);
                isJoin[i] = true;
                for (int j = i + 1; j < strs.length; j++) {
                    boolean flag = isAnagram(strs[i], strs[j]);
                    if (flag) {
                        string.add(strs[j]);
                        isJoin[j] = true;
                    }
                }
                strings.add(string);
            }
        }
        return strings;
    }*/

    /*public static List<List<String>> groupAnagrams(String[] strs) {
        //边界条件判断
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = new char[26];
            //统计字符串中每个字符串出现的次数
            for (char c : s.toCharArray()) {
                ca[c - 'a']++;
            }
            //统计每个字符出现次数的数组转化为字符串
            String keyStr = String.valueOf(ca);
            if (!map.containsKey(keyStr)) {
                map.put(keyStr, new ArrayList<>());
            }
            map.get(keyStr).add(s);
        }
        //map.values()：将map的所有value封装成一个集合并返回
        return new ArrayList<>(map.values());
    }*/


    /*public static boolean isAnagram(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] count = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            count[s1.charAt(i) - 'a']++;
        }
        for (int j = 0; j < s2.length(); j++) {
            count[s2.charAt(j) - 'a']--;
            if (count[s2.charAt(j) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }*/

    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String,List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] ch = new char[26];
            for (int j = 0; j < strs[i].length(); j++) {
                ch[strs[i].charAt(j) - 'a']++;
            }

            String keyStr = String.valueOf(ch);
            if (!map.containsKey(keyStr)) {
                map.put(keyStr,new ArrayList<>());
            }
            map.get(keyStr).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) throws InterruptedException {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = groupAnagrams(strs);
        System.out.println(lists.toString());

        /*Map<String,List<String>> map = new HashMap();
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        map.put("abc",list);
        List<String> list1 = new ArrayList<>();
        list1.add("e");
        list1.add("f");
        list1.add("g");
        map.put("efg",list1);
        List<String> list2 = new ArrayList<>();
        list2.add("h");
        list2.add("i");
        list2.add("j");
        map.put("hij",list2);
        System.out.println(map.values().toString());
        List<List<String>> values = (List<List<String>>) map.values();
        List<List<String>> lists = new ArrayList<>(map.values());
        System.out.println(lists.toString());*/
    }
}
//leetcode submit region end(Prohibit modification and deletion)
